package LC;

import java.util.Stack;

/**
 * https://leetcode.com/problems/maximal-rectangle/description/
 * Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
 * For example, given the following matrix:
 * 1 0 1 0 0
 * 1 0 1 1 1
 * 1 1 1 1 1
 * 1 0 0 1 0
 * Return 6.
 */
public class LC_085_MaximalRectangle_Matrix_Greedy {
    public static void main(String[] args) {
        char[][] a = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        int s = Solution.maximalRectangle(a);
        System.out.println(s);
    }

    static class Solution {
        static int maximalRectangle(char[][] matrix) {
            int m = matrix.length;
            int n = m == 0 ? 0 : matrix[0].length;
            int[][] height = new int[m][n + 1];

            int maxArea = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '0')
                        height[i][j] = 0;
                    else
                        height[i][j] = i == 0 ? 1 : height[i - 1][j] + 1;
                }
            }

            for (int i = 0; i < m; i++) maxArea = Math.max(maxAreaInHist(height[i]), maxArea);
            return maxArea;
        }

        private static int maxAreaInHist(int[] height) {
            Stack<Integer> stack = new Stack<>();
            int i = 0;
            int max = 0;

            while (i < height.length) {
                if (stack.isEmpty() || height[stack.peek()] <= height[i])
                    stack.push(i++);
                else {
                    int t = stack.pop();
                    max = Math.max(max, height[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
                }
            }

            return max;
        }
    }
}
